theoretical computer science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ...

and

formal language theory In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...

, the complementation of an is the problem of computing an automaton that accepts precisely the words rejected by another automaton. Formally, given an automaton ''A'' which recognizes a

regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...

''L'', we want to compute an automaton recognizing precisely the words that are not in ''L'', i.e., the

complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-clas ...

of ''L''. Several questions on the complementation operation are studied, such as: * Its computational complexity: what is the complexity, given an automaton, of computing an automaton for the complement language? * Its

state complexity State complexity is an area of theoretical computer science dealing with the size of abstract automata, such as different kinds of finite automata. The classical result in the area is that simulating an n-state nondeterministic finite automaton by ...

: what is the smallest number of states of an automaton recognizing the complement?

With deterministic finite automata

With nondeterministic finite automata

With a

nondeterministic finite automaton In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if * each of its transitions is ''uniquely'' determined by its source state and input symbol, and * reading an input symbol is required for each state ...

, the

of the complement automaton may be exponential. Lower bounds are also known in the case of unambiguous automata.

With deterministic finite automata

With nondeterministic finite automata

With two-way automata

With Büchi automata

See also

References